package Demo01;

public class Test {

}

class Solution {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t));
    }
    public static String minWindow(String s, String t) {
        if(t.length()>s.length()) {
            return "";
        }
        int[] cnts = new int[256];
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        for (char c : tt) {
            cnts[c]--;
        }
        //对t字符串进行负债处理
        int r = 0;
        int debt = tt.length;
        int start = 0;
        int l = 0;
        int min = Integer.MAX_VALUE;
        while (r < s.length()) {
            char c = ss[r];
            if (cnts[c]++ < 0) {
                debt--;
            }

            if (debt == 0) {
                //从后往前进行缩减
                while (cnts[ss[l]] > 0) {
                    cnts[ss[l++]]--;
                }
                if (min > r - l + 1) {
                    start = l;
                    min = r - l + 1;
                }
            }
            r++;
        }
        return (min==Integer.MAX_VALUE) ? "" : s.substring(start, start + min) ;
    }
}

